1. Field of the Invention
The field of the invention relates to the dynamic and concurrent restructuring of B.sup.+ -Tree storage structures. More generally, the invention relates to a system and method of semantically consistent dynamic restructuring of, and access to, large data bases.
2. Related Art
A concurrent B-Tree system and method can achieve more parallelism than standard concurrency control methods. The literature contains several concurrent search structure algorithms such as: the lock-coupling technique by Bayer, et al., "Concurrency of Operations on B-Trees", Acta Information, Vol. 9, No. 1, p1-21, 1977; the B.sup.link -Tree storage model by Lehman, et al., "Efficient Locking for Concurrent Operations on B-Trees", ACM Transactions on Database Systems, Vol. 6, No. 4, Dec. 1981; the give-up technique by Shasha, et al., "Concurrent Search Structure Algorithms", ACM Transactions on Database Systems, Vol. 13, No. 1, Mar. 1988; and the ARIES/IM system, see Mohan, et al., "ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write Ahead Logging", IBM Research Report 1989.
Consider the ARIES/IM system. During traversal, a special "SM" bit on each page involved in a structural modification operation (SMO) must be checked. If the SM bit is on, then the traverser requests and holds a tree latch until the SMO has completed. Thus, the ARIES/IM system does not permit fetches to traverse the tree until the structural modification operation is complete.